package com.fwpsl.graph.stronglyconnectedcomponent;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/5/1
 * @description: Kosaraju算法是一种用于在有向图中找到强连通分量的算法。这个算法由两个深度优先搜索（DFS）遍历组成。
 * 首先，对原图进行反向（即所有边的方向反转）的DFS遍历，并记录每个节点的完成时间（即DFS遍历中该节点被访问完成的时间）。
 * 然后，按照完成时间的降序对节点进行排序。最后，根据排序结果对原图进行DFS遍历，每次遍历会找到一个强连通分量。
 */
public class Kosaraju<T> {
    //    private Deque<Vertex<T>> stack; // 用于DFS的栈
//    private int time; // DFS的时间戳
    private Graph<T> graph;

    Kosaraju(Graph<T> graph) {
        this.graph = graph;
//        visited = new boolean[graph.getVertexNum()];
//        stack = new LinkedList<>();
//        time = 0;
    }


    public Deque<Vertex<T>> fillOrder() {
        Integer vertexNum = graph.getVertexNum();

        Deque<Vertex<T>> stack = new LinkedList<>();
        // Step 1: 反向DFS
        Map<Vertex<T>, Boolean> reverseVisitedMap = new HashMap<>();
//        Map<Vertex<T>, Integer> finishTimeMap = new HashMap<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            if (!reverseVisitedMap.getOrDefault(vertex, Boolean.FALSE)) {
                fillOrder(vertex, reverseVisitedMap, stack);
            }
        }

        return stack;
    }

    // 反向DFS，用于标记完成时间
    private void fillOrder(Vertex<T> vertex, Map<Vertex<T>, Boolean> reverseVisitedMap, Deque<Vertex<T>> stack) {
        reverseVisitedMap.put(vertex, Boolean.TRUE);

        Iterator<Edge<T>> i = vertex.getEdges().listIterator();
        while (i.hasNext()) {
            Vertex<T> destination = i.next().getDestination();
            if (!reverseVisitedMap.getOrDefault(destination, Boolean.FALSE)) {
                fillOrder(destination, reverseVisitedMap, stack);
            }
        }

//        finishTime[(int) vertex.getData()] = time++;
        stack.push(vertex);
    }

    // 根据完成时间进行DFS，找到强连通分量
    void printSCCsUtil(Vertex<T> vertex, Map<Vertex<T>, Boolean> visitedMap, Deque<Vertex<T>> resultStack) {
        visitedMap.put(vertex, Boolean.TRUE);

        Iterator<Edge<T>> i = vertex.getEdges().listIterator();
        while (i.hasNext()) {
            Vertex<T> destination = i.next().getDestination();
            if (!visitedMap.getOrDefault(destination, Boolean.FALSE)) {
                printSCCsUtil(destination, visitedMap, resultStack);
            }
        }

        // 将当前节点加入结果栈中
        resultStack.push(vertex);
    }

    // 打印强连通分量
    public void printSCCs() {

        Deque<Vertex<T>> stack = fillOrder();

        // 根据完成时间排序（这里简单起见，使用了一个Stack来模拟降序排序）

        // Step 2: 根据完成时间进行DFS
        Map<Vertex<T>, Boolean> visitedMap = new HashMap<>();

        Deque<Vertex<T>> resultStack = new LinkedList<>();

        // 遍历stack中的节点（降序），进行DFS
        while (!stack.isEmpty()) {
            Vertex<T> vertex = stack.pop();

            if (!visitedMap.getOrDefault(vertex, Boolean.FALSE)) {
                printSCCsUtil(vertex, visitedMap, resultStack);

                // 输出强连通分量
                System.out.println("Strongly Connected Component:");
                while (!resultStack.isEmpty()) {
                    System.out.print(resultStack.pop().getData() + " ");
                }
                System.out.println();

                // 清空结果栈以寻找下一个强连通分量
                while (!resultStack.isEmpty()) {
                    resultStack.pop();
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph<Integer> graph = new Graph();

        graph.addEdge(1, 0);
        graph.addEdge(0, 2);
        graph.addEdge(2, 1);
        graph.addEdge(0, 3);
        graph.addEdge(3, 4);
        graph.addEdge(3, 2);

        System.out.println("Following are strongly connected components");

        Kosaraju<Integer> kosaraju = new Kosaraju<>(graph);
        kosaraju.printSCCs();
    }
}
